package org.evosuite.ga.operators.ranking;

import java.util.*;

public class LinearGreedySetCover<K,  V> {

    public List<K> getMinimal(Map<K, Set<V>> allSet) {
        int max = -1;
        Map<Integer, List<K>> A = new HashMap<>();
        for(K k :allSet.keySet()) {
            int t = allSet.get(k).size();
            if(max < t) {
                max = t;
            }
            int size =   allSet.get(k).size();
            if(!A.containsKey(size)) {
                A.put(size, new ArrayList<>());
            }
            A.get(size).add(k);
        }
        Map<V, List<K>> L = new HashMap<>();
        allSet.forEach((k,vs)->{
            vs.forEach(v->{
                if(!L.containsKey(v)) {
                    L.put(v, new ArrayList<>());
                }
                L.get(v).add(k);
            });
        });
        List<K> ret = new ArrayList<>();
        List<V> covered = new ArrayList<>();
        while(max > 0) {
            K k = A.get(max).get(0);
            ret.add(k);
            A.get(max).remove(k);
            Set<V> vs = new LinkedHashSet<>(allSet.get(k));
            vs.removeAll(covered);
           for(V sv : vs) {
               List<K> ak = L.get(sv);
               for(K aki : ak) {
                   int ts = allSet.get(aki).size();
                   A.get(ts).remove(aki);
                   allSet.get(aki).remove(sv);
                   ts--;
                   if(!A.containsKey(ts)) {
                       A.put(ts, new ArrayList<>());
                   }
                   A.get(ts).add(aki);
                   while (A.get(max) == null || A.get(max).size() == 0) {
                       max--;
                   }
               }
               covered.add(sv);
           }
        }
        return ret;
    }
}
